pq = require "priority_queues"

function alt_heap_sort(a) 
   local result = {} 
   local h = pq.build_heap(a)
   for i = #h,1,-1 do 
      -- pq.check_heap(h,i)
      local v = pq.extract_top(h) 
      a[i] = v
   end 
   --   assert_sorted(a,1,#a,"la")
   return a 
end 

function assert_sorted (a,start,finish,s) 
   local last = a[start] 
   for i = start+1, finish do 
      assert((last <= a[i]), 
	     string.format("%s: value %d at %d\n", s, a[i], i)) 
      last = a[i]
   end
end 

function alt_heap_sort_cp_steps (st,reps,step) 
	local t = {} 
	for j = 0,reps-1 do 
		local a = {}   
		
		for i=1,st+(step*j) do
			a[i]=math.random(1,100)
		end 
		
		--      print("a: ", unpack(a)) 
		local t0 = os.clock() 
		local h = pq.build_heap(a) 
		--      pq.check_heap(h,st+(step*j))
		local a1 = alt_heap_sort(h)
		local t1 = os.clock() 
		--      print("\na1: ", #a1)
		assert_sorted(a1,1,#a1,"alt_heap")
		t[j] = t1-t0; io.write(string.format("%f ", t[j])); io.flush() 
   end
   io.write("\n") 
   return t 
end

function tabular_differences(t)
   local last = t[1]
   local diff_table = {} 
   for i=2,#t do 
      diff_table[i-1] = t[i]-last 
      last = t[i]
   end
   return diff_table 
end

function sum_table (t) 
   local sum = 0 
   for i=1,#t do sum = sum+t[i] end 
   return sum 
end 

alt_heap_sort_cp_steps (10,100,100) 

